#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define ElemType int
#define Status int


typedef struct LNode{
	ElemType data;
	LNode *next;
}*Link,*Position;

typedef struct {
	Link head,tail;//头结点，尾部节点
	int len;//节点的个数
}LinkList;

typedef Status(*fp)(Link , Link);


// 创建一个空的链表
void CreateList_L(LinkList &L);
// 返回链表第i个位置的结点位置
Status LocatePos(LinkList L,int i,Link &p);
// 分配一个节点值指向e
Status MakeNode(Link &p,ElemType e);
// 把节点s插入到h之后
Status InsFirst(Link h,Link s);
// 在第i个节点前插入数据为e的节点
Status InsertList_L(LinkList &L,int i,ElemType e);
// 获取LinkList的根节点
Link GetHead(LinkList L);
Status MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc,fp compare);

// 创建一个空的链表
void CreateList_L(LinkList &L){
	Link p;
	p = (Link)malloc(sizeof(LNode));
	p->next = NULL;
	L.head = p;L.tail = p;
	L.len = 0;
}

// 返回链表第i个位置的结点位置
Status LocatePos(LinkList L,int i,Link &p){
	// if(i<0 || i>L.len) return ERROR;
	p = L.head;
	while(!p && i--) p=p->next;
	return OK;	
}

// 分配一个节点值指向e
Status MakeNode(Link &p,ElemType e){
	p = (Link)malloc(sizeof(LNode));
	if(!p)return ERROR;
	p->data = e;
	return OK;
}

// 把节点s插入到h之后
Status InsFirst(Link h,Link s){
	s->next = h->next;
	h->next = s;
	if(!s->next || !h->next)return ERROR;
	return OK;
}

Status InsertList_L(LinkList &L,int i,ElemType e){
	Link h,s;
	if(!LocatePos(L,i-1,h)) return ERROR;
	if(!MakeNode(s,e)) return ERROR;
	InsFirst(h,s);
	return OK;
}
// 获得根节点
Link GetHead(LinkList L){
	return L.head;
}
// 获取S下一个节点
Link NextPos(Link s,Link p){
	return p->next;
}
ElemType GetCurElem(Link p){
	return p->data;
}
// 删除h后的一个节点，该节点用q返回
void DelFirst(Link h,Link &q){
	q = h->next;
	h->next = h->next->next;
} 
void Append(LinkList L,Link p){
}
Status showListData(LinkList L){
	// 去除头结点
	Link elem;
	elem = L.head->next;
	if(!elem)
		return ERROR;
	while(elem){
		printf("%d\n", elem->data);
		elem = elem->next;
	}
}
// a<b retun 1
Status Less(Link a,Link b){
	if(a->data < b->data)
		return OK;
	else
		return ERROR;
}
Status MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc,fp compare){
	Link ha,hb;
	Link pa,pb,pc;
	// 获取头结点
	ha = La.head;hb = Lb.head;
	// 第一个节点
	pa = ha->next;pb = hb->next;
	// c的头结点
	Lc.head = pc = ha;
	while(pa && pb){
		if(compare(pa,pb)){
			pc->next = pa;
			pa = pa->next;
		}
		else{
			pc->next = pb;
			pb = pb->next;
		}
		pc = pc->next;
	}
	if(pa)
		pc->next = pa;
	else
		pc->next = pb;
	free(hb);
	return OK;
}